By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 37, Issue 6, pp. vii-1952

Please Note: Electronic articles are available well in advance of the printed articles.

Special Issue: Foundations of Computer Science
What Article options are available ?   View Cart   

Special Issue on Foundations of Computer Science

Irit Dinur and Eva Tardos

p. vii

BibTeX  Abstract Full Text:  PDF

A Characterization of the (Natural) Graph Properties Testable with One-Sided Error

Noga Alon and Asaf Shapira

pp. 1703-1727

BibTeX  Abstract Full Text:  PDF

An Algorithmic Version of the Hypergraph Regularity Method

P. E. Haxell, B. Nagle, and V. Rödl

pp. 1728-1776

BibTeX  Abstract Full Text:  PDF

Agnostically Learning Halfspaces

Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio

pp. 1777-1805

BibTeX  Abstract Full Text:  PDF

Lower Bounds for the Noisy Broadcast Problem

Navin Goyal, Guy Kindler, and Michael Saks

pp. 1806-1841

BibTeX  Abstract Full Text:  PDF

The Symmetric Group Defies Strong Fourier Sampling

Cristopher Moore, Alexander Russell, and Leonard J. Schulman

pp. 1842-1864

BibTeX  Abstract Full Text:  PDF

Cryptography in the Bounded-Quantum-Storage Model

Ivan B. DamgÅrd, Serge Fehr, Louis Salvail, and Christian Schaffner

pp. 1865-1890

BibTeX  Abstract Full Text:  PDF

Concurrent Nonmalleable Commitments

Rafael Pass and Alon Rosen

pp. 1891-1925

BibTeX  Abstract Full Text:  PDF

A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights

Philip N. Klein

pp. 1926-1952

BibTeX  Abstract Full Text:  PDF